# -*- coding: utf-8 -*-

"""LRU缓存淘汰算法：least recently used，最近最少使用着淘汰

先假设当前缓存的数据是个黑盒，里面有<A,B,C>，
一. 先看基本功能：
现在要查询D，需要遍历缓存ABC，发现没有，录入D；
再查询E，需要遍历缓存ABCD，发现没有，录入E；
再查询F，需要遍历缓存ABCDE，发现没有，录入F；
再查询G，需要遍历缓存ABCDEF，发现没有，录入G；
...
再录入若干新的缓存
...
再查询Z时，遍历A-Y，发现没有，需要录入Z，但是缓存容量超过上限，需要淘汰最近最少使用的，那么肯定要淘汰很久没有使用过的，那么可以使用一个线性表来存储缓存，按最近使用顺序来排列缓存元素

D --> E --> F --> G --> H --> I --> ...

若查询E时，在缓存中遍历到E，则应该将E放到最近使用的位置
D --> F --> G --> H --> I --> ... --> E

从这个缓存结构可以看出，每次操作之后各元素之间需要保持顺序，所以用连续内存的数组，开销比较大，但单向链表可以就可以实现得比较好

一. 优化
LRU是鼓励最近使用得缓存使用得越多，每次查询得时候需要遍历缓存，按上面方案，每次查询都是从最老使用过的缓存开始遍历，要知道，最老的缓存是给淘汰的，最近的缓存被查询到的几率大
所以我们可不可以换个方向遍历，每次从最近使用的元素开始遍历缓存，找到该元素时终止遍历？
... E -->  --> I --> H --> G --> F --> D

E --> ...  --> I --> H --> G --> F --> D

使用逻辑：
在缓存中查询
    查询到目标，则提高该目标查询容易度
    没有查询到目标，则向缓存中录入
        若缓存还有容量，直接录入，容易度高
        若缓存已满，淘汰掉最近最少使用者，再直接录入，容易度高
"""

from classic.linkedlist import SingleLinkedList

class LRU(object):
    def __init__(self, size) -> None:
        self.size = size
        self.cache = SingleLinkedList()
    
    def search(self, x):
        try:            
            i = self.cache.find_item(x)
            self.cache.remove(i)
            self.cache.insert(0, x)
        except KeyError:
            self.record(x)

    def record(self, x):
        if self.cache.length >= self.size:
            self.cache.pop()
        self.cache.insert(0, x)


if __name__ == '__main__':
    lru = LRU(5)
    lru.search('a')
    lru.search('b')
    lru.search('c')
    lru.search('d')
    lru.search('e')
    lru.search('f')

    for i in lru.cache:
        print(i, end=',')    
    print('')

    lru.search('c')

    for i in lru.cache:
        print(i, end=',')    
    print('')
